package Algorithm.SearchAlgorithmDome;

import java.util.Scanner;

/**
 * ClassName:BlockSearch
 * Package:Algorithm.SearchAlgorithmDome
 * Description:
 *
 * @Author:ZhangXin
 * @Create2023/2/4-0:00
 * @Version:v1.0
 */
public class BlockSearch001 {
    /*分块查找*/
    /*
     * 分块原则1：前一块中的最大数据,小于后一块中的所有数据(块内无序,块间有序)
     * 分块原则2：块数数量一半等于数字的个数开根号.比如：16个数字一般分为4块左右
     * 核心思路：先确定要查找的元素在哪一块,然后在块内挨个查找
     *
     * 实现步骤
     * 1：创建数组blockArr存放每一个块对象的信息
     * 2：先查找blockArr确定要查找的数据属于哪一块
     * 3：在单独遍历这一块数据即可
     * */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入你要查找的数据：");
        int[] arr = {16, 5, 9, 12, 21, 18,
                32, 23, 37, 26, 45, 34,
                50, 48, 61, 52, 73, 66};
        //要把数据进行分块
        //要分为几块：18 开根号  4.25块
        //18/4 = 4.5个

        //创建三个块的对象
        Block b1 = new Block(21, 0, 5);
        Block b2 = new Block(45, 6, 11);
        Block b3 = new Block(73, 12, 17);

        //定义数组用来管理三个块的对象(索引表)
        Block[] blockArr = {b1, b2, b3};
        //定义一个变量用来记录要查找的元素
        int number = sc.nextInt();
        //调用方法,传递索引表,数组,要查询的元素
        int index = getIndex(arr, blockArr, number);
        if (index >= 0) {
            System.out.println(number + "在数组中的" + index + "索引上");
        } else {
            System.out.println("该数不存在数组中!");
        }
    }


    //利用分块查找的原理,查询number的索引
    private static int getIndex(int[] arr, Block[] blockArr, int number) {
        //确定number在哪一块中
        int indexBlock = findIndexBlock(blockArr, number);
        if (indexBlock < 0) {
            //表示number不在数组当中
            return -1;
        }
        //获取这一块的起始索引和结束索引
        int startIndex = blockArr[indexBlock].getStartIndex();
        int endIndex = blockArr[indexBlock].getEndIndex();

        //遍历
        for (int i = startIndex; i <=endIndex; i++) {
            if (arr[i] == number) {
                return i;
            }
        }
        return -1;
    }

    //定义一个方法,确定number在哪一块
    public static int findIndexBlock(Block[] blockArr, int number) {
        //Block b1 = new Block(21, 0, 5);    ----0
        //Block b2 = new Block(45, 6, 11);   ----1
        //Block b3 = new Block(73, 12, 17);  ----2

        //从0 索引开始遍历blockArr,如果number小于max,那么就表示number是在这一块中
        for (int i = 0; i < blockArr.length; i++) {
            if (number <= blockArr[i].getMax()) {
                return i;
            }
        }
        return -1;
    }
}






class Block {
    private int max;//块中的最大值
    private int startIndex;//起始索引
    private int endIndex;//结束索引

    public Block() {
    }

    public Block(int max, int startIndex, int endIndex) {
        this.max = max;
        this.startIndex = startIndex;
        this.endIndex = endIndex;
    }

    /**
     * 获取
     *
     * @return max
     */
    public int getMax() {
        return max;
    }

    /**
     * 设置
     *
     * @param max
     */
    public void setMax(int max) {
        this.max = max;
    }

    /**
     * 获取
     *
     * @return startIndex
     */
    public int getStartIndex() {
        return startIndex;
    }

    /**
     * 设置
     *
     * @param startIndex
     */
    public void setStartIndex(int startIndex) {
        this.startIndex = startIndex;
    }

    /**
     * 获取
     *
     * @return endIndex
     */
    public int getEndIndex() {
        return endIndex;
    }

    /**
     * 设置
     *
     * @param endIndex
     */
    public void setEndIndex(int endIndex) {
        this.endIndex = endIndex;
    }

    public String toString() {
        return "Block{max = " + max + ", startIndex = " + startIndex + ", endIndex = " + endIndex + "}";
    }
}